\chapter{Plan de transfert des requ\^etes} \label{chap:Plan de transfert des requ\^etes}
\minitoc

%avec le routage dans les r\'eseaux informatiques 
\ochap{L}{e} pr\'esent chapitre d\'etaille les aspects relatifs au traitement des requ\^etes de recherche dans PosNet.
Par analogie avec le plan de transfert dans les routeurs IP (en anglais << forwarding plane >>), nous parlons de \emph{plan de transfert des requ\^etes} de PosNet.

Nous avons d\'efini au chapitre pr\'ec\'edent les chemins sans vall\'ee ; nous proposons dans ce chapitre 
%un \emph{routage sans vall\'ee}, nous permettant de formuler un ensemble d'algorithmes de r\'esolution de requ\^etes de recherche
%bas\'es sur des plus courts chemins sans vall\'ee.
un \emph{routage sans vall\'ee}. Le routage sans vall\'ee regroupe une famille d'algorithmes de recherche ayant pour point commun de s\'electionner uniquement des chemins sans vall\'ee lors de l'acheminement des requ\^etes dans l'overlay PosNet.
%Nous montrons \`a travers ces algorithmes qu'il est possible en s\'electionnant des plus courts chemins sans vall\'ee pour acheminer les requ\^etes dans l'overlay PosNet de r\'esoudre l'ensemble des types de requ\^etes qui nous int\'eressent tout en \'elaguant l'espace de recherche. 
A travers ces algorithmes, nous d\'emontrons qu'il est possible gr\^ace aux chemins sans vall\'ee de r\'esoudre l'ensemble des types de requ\^etes qui nous int\'eressent tout en \'elaguant l'espace de recherche.
%, nous montrons \`a travers ces algorithmes qu'il est possible de r\'esoudre l'ensemble des types de requ\^etes qui nous int\'eressent tout en \'elaguant l'espace de recherche. 
%Ces algorithmes permettent de r\'esoudre l'ensemble des types de requ\^etes qui nous int\'eressent tout en \'elaguant l'espace de recherche. 
%Le chapitre est d\'ecoup\'e en 6 parties : \ref{sec:Routage sans vall\'ee} porte sur les principes du routage sans vall\'ee, les 4 

Le chapitre est organis\'e de la mani\`ere suivante. Les principe du routage sans vall\'ee sont d\'ecrits en \ref{sec:Routage sans vall\'ee} 
en trois temps. Nous donnons tout d'abord une vue g\'en\'erale du cheminement d'une requ\^ete de recherche dans un PosNet. Puis nous d\'ecrivons le processus de routage au niveau local d'un pair, que nous \'etendons ensuite \`a l'environnement distribu\'e de l'overlay.
Une fois expliqu\'e le routage sans vall\'ee, le reste du chapitre est consacr\'e \`a ses applications aux algorithmes de recherche
dans PosNet : le cas des recherches de point est trait\'e en \ref{sec:Requetes exactes} et celui des recherches d'intervalles en \ref{sec:Requetes par intervalles}. Les requ\^etes avec joker ainsi que les requ\^etes skyline sont trait\'ees
\`a part dans \ref{sec:??}. Nous montrons notamment que le front de Pareto de l'ensemble des donn\'ees index\'ees
est obtenu directement par exploitation des propri\'et\'es structurelles du pograph. 
Avant de conclure bri\`evement, nous exposons en \ref{sec:remarquesimplem} quelques morceaux choisis de l'impl\'ementation. 

%On a vu dans le chapitre 
%
%Les aspects statiques de PosNet ont fait l'objet du chapitre \og Probl\'ematique \fg{},
%avec entre autres la description de la structure d'acc\`es : le graphe
%s\'emantique. A partir du graphe s\'emantique, on a d\'efini la notion de
%chemin sans vall\'ee. Ces chemins sans vall\'ee vont nous permettre de
%d\'efinir les algorithmes de r\'esolution de requ\^etes. Le pr\'esent chap\^etre
%d\'eveloppe ces algorithmes, sous la forme de protocoles de routage
%dans PosNet.

%\paragraph{{[}\underbar{A FAIRE un lexique ! Notation employ\'ee :} noeud s\'emantique
%| pair (pour un noeud de l'overlay) | algorithme de routage | recherche
%| solution | valeur | chemin descendant/ascendant | clique, membre
%de/appartenir\`ala clique | traverser (un n\oe ud- pour une requ\^ete)
%| \'evaluer (une requ\^ete - pour un pair) | croiser (un n\oe ud- pour
%une requ\^ete) | noeud courant | noeud feuille | cha\^ines | pair englobant
%| contenir (une valeur, une requ\^ete, un noeud s\'emantique, un pair)
%| englobant (pour un pair) | donn\'ee recherch\'ee | valeur du point |
%requ\^ete | noeud enfant/enfant | noeud parent/parent | ascension, descente
%| saut | cheminement | voisin de clique | solution | point | valeur
%(clarifier la notion de \og solution de valeur \fg{}, \og solution
%repr\'esent\'ee par un point \fg{}) | r\'egion} | partition de graphe s\'emantique


%\section{Traitement des requ\^etes}
\section{Routage sans vall\'ee} \label{sec:Routage sans vall\'ee}
\subsection{Traitement g\'en\'eral d'une requ\^ete de recherche dans PosNet} \label{subsec:Principes g\'en\'eraux}
%Dans une (hypoth\'etique) architecture centralis\'ee de PosNet, o\`u un (ou plusieurs) noeud(s) poss\'ederai(en)t la connaissance compl\`ete du graphe s\'emantique, 
%la localisation d'une donn\'ee se ram\`enerait\`a une (ou plusieurs) recherche(s) de chemin(s) sans vall\'ee dans ce graphe complet, en local dans la m\'emoire interne d'un noeud. 
%Or une architecture d\'ecentralis\'ee implique que le graphe s\'emantique soit distribu\'e : chaque noeud ne poss\`ede qu'un sous-graphe du graphe s\'emantique global. Une des 
%cons\'equences de la distribution du graphe s\'emantique est l'accroissement de la complexit\'e du routage : une recherche de chemin peut n\'ecessiter la coop\'eration 
%de plusieurs noeuds (les noeuds par les graphes s\'emantiques locaux desquels passe le chemin). Dans un contexte d\'ecentralis\'e, on voit donc appara\^etre la n\'ecessit\'e 
%d'un protocole suppl\'ementaire, li\'e\`a la communication entre noeuds de l'overlay. 
Une requ\^ete de recherche \'emise par une application cliente est inject\'ee dans PosNet \emph{via} un pair quelconque de l'overlay. 
Lors de son traitement, elle est achemin\'ee de pair en pair.  
Chaque pair travers\'e contribue \`a la r\'esolution de la requ\^ete de deux mani\`eres. 
Premi\`erement, lorsqu'il connait une ou plusieurs solutions satisfaisant la requ\^ete, il retourne celles-ci. 
Deuxi\`emement, il propage la requ\^ete aux pairs voisins susceptibles de connaitre des solutions.
Un pair proc\`ede \`a l'\'evaluation d'une requ\^ete en calculant un ou plusieurs chemins sans vall\'ee dans sa partition du pograph. 
Les chemins calcul\'es permettent de d\'eterminer les solutions \`a retourner et les prochains pairs auxquels transmettre la requ\^ete. 
On peut comparer une partition du pograph \`a une table 
de routage, car elle permet de d\'eterminer le ou les prochains sauts dans le r\'eseau overlay (m\^eme si dans notre cas, le routage n'est pas guid\'e par une destination connue \`a l'avance). 
Le chemin d'une requ\^ete dans l'overlay est construit incr\'ementalement de pair en pair. 
%: le choix des liens emprunt\'es vers les noeuds s\'emantiques $n+1$ se fait aux noeuds $n$. 
%Le calcul des chemins sans vall\'ee effectu\'e par un pair pour traiter une requ\^ete s'effectue \'egalement de mani\`ere incr\'ementale, dans sa partition du pograph. 
Des noeuds s\'emantiques d'entr\'ee, aux noeuds s\'emantiques de sortie ou jusqu'\`a l'arr\^et du traitement de la requ\^ete, les chemins sont construits de proche en proche. En 
particulier, les liens inter-noeuds s\'emantiques successivement emprunt\'es sont s\'electionn\'es \`a chaque noeud s\'emantique. On pourra remarquer que pour une requ\^ete donn\'ee, 
la s\'equence des chemins sans vall\'ee calcul\'es localement par chaque pair forme des chemins sans vall\'ee dans le pograph global. La jonction entre deux chemins 
cons\'ecutifs, calcul\'es par des pairs distincts, se traduit par un saut dans l'overlay (un envoi de message entre deux pairs). Les routes emprunt\'ees par une requ\^ete dans 
l'overlay sont enti\`erement d\'etermin\'ees par les chemins sans vall\'ee construits dans le pograph global sous-jacent. 
%On rappelle ici une propri\'et\'e essentielle du pograph : l'existence d'au moins un chemin sans vall\'ee entre toute paire de sommets dans le graphe.
[TODO Reprendre le sh\'ema en \'evitant les codes couleur + en distinguant les pairs des simples h\'ebergeurs]

% \begin{figure}[!h]
% \begin{center}
% \epsfig{file=fig/plan_transfert_requetes_general%,scale=1
% }
% \label{fig:plantransfertrequetesgeneral}
% \caption{Illustration des correspondances entre chemins sans vall\'ee dans le pograph, chemins sans vall\'ees calcul\'es localement par un pair sur une partition du 
% pograph, route d'une requ\^ete dans l'overlay, route d'une requ\^ete dans l'underlay.}
% \end{center}
% %\label{fig:4}
% \end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=0.7\textwidth]{fig/plan_transfert_requetes_general}
\caption{Illustration des correspondances entre chemins sans vall\'ee dans le pograph, chemins sans vall\'ees calcul\'es localement par un pair sur une partition du 
pograph, route d'une requ\^ete dans l'overlay, route d'une requ\^ete dans l'underlay.}
\label{fig:plantransfertrequetesgeneral}
\end{figure}
 
%\subsection{Plan du chapitre} 
Nous distinguons deux niveaux dans la pr\'esentation du processus de r\'esolution d'une requ\^ete dans PosNet :
\begin{description}
\item \textbf{Le guidage dans le pograph} : la construction de chemins sans vall\'ee dans un pograph ; 
\item \textbf{Le routage dans l'overlay} : la construction des routes correspondant aux chemins sans vall\'ee dans un graphe des pairs. 
\end{description}

% Dans un premier temps, nous pr\'esentons le guidage dans le pograph en d\'ecrivant les diff\'erents algorithmes de recherche de chemins sans vall\'ee en fonction du type des requ\^etes.
% Puis dans un second temps, nous \'etablissons la correspondance entre ces chemins s\'emantiques et les routes emprunt\'ees dans l'overlay.
Pour all\'eger la formulation, en l'absence d'ambiguit\'e on assimile \`a un n\oe ud  du pograph sa valeur associ\'ee. Par exemple, le n\oe ud  du pograph associ\'e \`a la solution $(3,2)$ 
sera d\'esign\'e par $(3,2)$. De la m\^eme mani\`ere, on assimilera une requ\^ete aux donn\'ees recherch\'ees. Par exemple $RE(3,2)$ sera confondu avec $(3,2)$. Enfin on parlera de \og 
monter \fg{} (respectivement \og descendre \fg{}) une requ\^ete pour exprimer la propagation d'une requ\^ete vers un n\oe ud  parent (respectivement enfant) du n\oe ud du pograph 
courant. 

\subsection{Guidage dans le pograph} \label{subsec:Guidage dans le pograph}

%\subsection{Principes g\'en\'eraux du guidage dans le pograph}

%\paragraph{Calcul distribu\'e de chemins sans vall\'ee dans le pograph}
%\subsection{Calcul distribu\'e de chemins sans vall\'ee dans le pograph}
Le pograph de l'espace des solutions est distribu\'e sur l'ensemble des pairs de l'overlay. Chaque pair traite les requ\^etes en calculant localement des chemins 
sans vall\'ee dans sa partition du pograph. On peut consid\'erer PosNet comme un \emph{framework} algorithmique de recherche, car de multiples algorithmes de 
localisation de donn\'ees peuvent utiliser des chemins sans vall\'ee. \\
%le pograph permet de multiples algorithmes de parcours sans vall\'ee, correspondant \`a autant de types de requ\^etes. \\
Les pairs de l'overlay appliquent l'algorithme de guidage dans le pograph qui convient en fonction du type de requ\^ete \`a traiter. PosNet permet d\'ej\`a la r\'esolution de plusieurs 
types de requ\^etes. On trouvera dans ce chapitre les algorithmes correspondant aux requ\^etes de type : exacte, par intervalle, \emph{wildcard}, %*k*-plus proches voisins,
 \emph{skyline}. En particulier, on s'int\'eresse ici au cas de la relation d'ordre partiel de l'ordre produit, cf. chapitre \ref{chap:Probl\'ematiques et pr\'esentation g\'en\'erale de PosNet}. \\
Le fonctionnement d\'ecentralis\'e de PosNet va de pair avec la r\'epartition des traitements et des donn\'ees. La recherche de chemins sans vall\'ee  doit se faire de mani\`ere 
distribu\'ee, chaque pair ayant un acc\`es limit\'e aux autres pairs (limit\'e \`a ses voisins) et au pograph (limit\'e \`a sa partition).  
%Comme expos\'e au d\'ebut de ce chapitre, la r\'esolution de requ\^ete est pens\'ee comme un processus coop\'eratif entre les pairs de l'overlay. 
Les pairs sont des entit\'es fonctionnelles homog\`enes, interchangeables, fonctionnant de mani\`ere coop\'erative (cf. Figure \ref{fig:queryrouting}). Leur processus de d\'ecision est 
identique : choix de l'algorithme de recherche de chemin appropri\'e \`a chaque type de requ\^ete et ex\'ecution it\'erative de cet algorithme. %Chaque pair parcouru par une m\^eme 
%requ\^ete ex\'ecute la m\^eme proc\'edure. Un algorithme de guidage dans le pograph d\'ecrit une it\'eration du processus de d\'ecision. 
A chaque it\'eration de l'algorithme, la relation binaire peut \^etre appliqu\'ee une ou plusieurs fois. 
L'ex\'ecution des algorithmes ne n\'ecessite des pairs qu'une connaissance partielle du syst\`eme. On remarquera que dans la plupart des cas, un pair seul ne poss\`ede pas 
suffisamment d'informations pour r\'esoudre enti\`erement une requ\^ete. Plus pr\'ecis\'ement, les seules informations que n\'ecessite l'\'evaluation d'une requ\^ete sont (quelque soit 
son type) : i) la connaissance des pairs adjacents et ii) le label du dernier lien travers\'e (illustration Figure \ref{fig:queryiteration}).  

\begin{figure}[!h] 
\centering
  \subfigure[Traitement de la requ\^ete $Q$ dans un pair. Dans cet exemple, $Q$ est propag\'ee \`a un pair adjacent.]
{\includegraphics[width=0.4\textwidth]{./fig/algorithm.png}\label{fig:queryrouting}}
%{\epsfig{file=fig/algorithm.png,width=6cm}\label{fig:queryrouting}}
  $\,$
	\subfigure[Illustration d'une it\'eration de l'algorithme de recherche de chemin dans un pograph au n\oe ud$P$.]
{\includegraphics[width=0.4\textwidth]{./fig/iteration.png}\label{fig:queryiteration}}
	%{\epsfig{file=fig/iteration.png,width=6cm}\label{fig:queryiteration}}
\end{figure}

\subsubsection{Interpr\'etation des phases ascendante, plate et descendante d'un chemin sans vall\'ee}
On a vu dans le chapitre de pr\'esentation de PosNet \ref{chap:Probl\'ematiques et pr\'esentation g\'en\'erale de PosNet} que la recherche de chemins sans vall\'ee constitue un invariant commun \`a tous les algorithmes de guidage 
dans le pograph, quelque soit le type de la requ\^ete ou la relation d'ordre partiel. On a \'egalement vu qu'un chemin sans vall\'ee typique peut se d\'ecrire comme une s\'equence d'arcs 
ascendants, suivi d'un arc plat, puis d'une s\'equence d'arcs descendants. Ces phases ascendantes, plates et descendantes correspondent \`a des phases distinctes de la recherche 
de solutions. 
\begin{description}
\item \textbf{Chemin ascendant} : Intuitivement, le chemin ascendant co\`uncide avec une recherche de n\oe ud  plus \og inform\'e \fg{}. La s\'equence de liens ascendants correspond 
\`a des comparaisons entre l'objet de la requ\^ete et une s\'equence de noeuds ou bien incomparables ou bien domin\'es par lui. En dernier ressort, la requ\^ete est compar\'ee \`a un n\oe ud
de la clique des \'el\'ements maximaux ;
\item \textbf{Arc plat} : La clique des \'el\'ements maximaux compose une vue globale des donn\'ees index\'ees dans le r\'eseau : si le n\oe ud  solution existe, alors il est ou bien 
maximal, ou bien contenu par un n\oe ud  maximal. Cette phase de la recherche n\'ecessite au plus un saut, du fait de l'organisation en clique des noeuds maximaux. Si au moins 
un n\oe ud  maximal contient la requ\^ete, la construction d'un chemin descendant est amorc\'e ;
\item \textbf{Chemin descendant} : Il correspond \`a un \og raffinement \fg{} de la recherche : si l'on descend c'est que l'on a trouv\'e un n\oe ud  qui contient tout ou partie 
de la requ\^ete. Par construction si une solution existe, alors elle se trouve parmi les enfants de ce n\oe ud . Le chemin descendant va suivre une cha\^ine \`a partir du n\oe ud
sup\'erieur qui l'a initi\'e.
\end{description}
Pour une requ\^ete donn\'ee, la phase ascendante suit en g\'en\'eral un seul chemin. En revanche, la phase descendante peut \^etre compos\'ee de plusieurs chemins descendants, parcourus 
en parall\`ele. 
Il est important de souligner que si un n\oe ud  contenant la requ\^ete est rencontr\'e en cours d'ascension, alors le chemin ascendant est interrompu et un chemin descendant est 
amorc\'e (si les noeuds enfants le permettent). En effet, il n'est pas n\'ecessaire de remonter une requ\^ete jusqu'aux noeuds maximaux si une borne sup\'erieure\footnote{La borne 
sup\'erieure est d\'efinie comme le plus petit des majorants.} de l'espace des solutions satisfaisant la requ\^ete est d\'ecouverte. Ces raccourcis dans le pograph permettent 
de r\'eduire la potentielle centralit\'e des noeuds maximaux. De plus dans l'hypoth\`ese o\`u l'espace des solutions est suffisamment large, une proportion significative des requ\^etes 
n'a pas besoin d'\^etre compar\'ee aux noeuds maximaux.  

\subsubsection{Interpr\'etation des vall\'ees et application au routage des requ\^etes}
Afin de mieux comprendre le r\^ole des vall\'ees et les raisons de leur interdiction par les algorithmes de guidage de requ\^etes, on d\'etaille
dans quels cas elles apparaissent et pourquoi elles conduiraient \`a explorer inutilement des noeuds du pograph.
Une vall\'ee peut appara\^itre lorsqu'\`a une it\'eration de l'algorithme le n\oe ud du pograph courant n'est pas un n\oe ud maximal et qu'il poss\`ede une valeur inf\'erieure ou 
incomparable \`a celle du point recherch\'e. Dans ce cas, la requ\^ete est suppos\'ee \^etre compar\'ee \`a un parent. Deux possibilit\'es se pr\'esentent alors, en fonction du label 
du lien pr\'ec\'edemment emprunt\'e : 
\begin{itemize}
\item{Le label pr\'ec\'edent est de type \og c2p \fg{} : le n\oe ud  courant est sur le chemin ascendant de la requ\^ete. Une transition ascendante (comparaison avec un parent) 
est donc un mouvement valide (qui conserve la validit\'e du chemin) ;}
\item{Le label pr\'ec\'edent est de type \og p2c \fg{} : le n\oe ud  courant est le r\'esultat d'un raffinement de la recherche. Or si sa valeur est inf\'erieure au point recherch\'e, 
alors inutile de comparer la requ\^ete avec un n\oe ud  parent : elle ne peut \^etre satisfaite car si le point recherch\'e existait, il se serait trouv\'e entre le pr\'ec\'edent 
n\oe ud(de valeur sup\'erieure) et lui-m\^eme (de valeur inf\'erieure). De m\^eme si sa valeur est incomparable, alors inutile de remonter la requ\^ete, car si le point recherch\'e 
existait, il existerait un autre enfant, unique, qui le contiendrait et par lequel serait pass\'ee la requ\^ete.}
\end{itemize}
Dans ces deux cas, le point recherch\'e ne peut pas \^etre trouv\'e en remontant la requ\^ete. La politique de guidage d'un n\oe ud  int\'egre cette contrainte sous la forme de 
chemins sans vall\'ee.
Les autres cas th\'eoriques d'apparition de vall\'ee sont les transitions de type : \og p2c-m2m \fg{}, \og m2m-c2p \fg{} et \og m2m-m2m \fg{}. Elles sont li\'ees \`a la d\'efinition 
m\^eme de noeux maximal et leur interpr\'etation est imm\'ediate. 
La figure \ref{fig:cheminsansvalleeinterpretation} reprend la figure \ref{fig:Reglescomposition} du chapitre \ref{chap:Probl\'ematiques et pr\'esentation g\'en\'erale de PosNet} et \'etend l'explication \og syntaxique \fg{} des vall\'ees en leur donnant une interpr\'etation algorithmique. 
\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/chemin_sans_vallee_interpretation,scale=0.8}
\caption{Interpr\'etation des situations d'apparition de vall\'ee lors de la recherche de chemin dans un pograph.\label{fig:cheminsansvalleeinterpretation}}
\end{center}
%\label{fig:4}
\end{figure}

%On d\'emontre maintenant la terminaison d'un algorithme de recherche de chemins sans vall\'ee. 
%\newline
%Un algorithme de recherche de chemins sans vall\'ee se termine car : 
On d\'emontre la terminaison d'un algorithme de recherche de chemins sans vall\'ee se termine car :   
\begin{enumerate}
	\item Un chemin sans vall\'ee est fini, car il n'existe pas dans le pograph de cha\^ine infinie (un chemin sans vall\'ee est de longueur maximum $2*d+1$, avec $d$ le diam\`etre du graphe) et qu'un chemin sans vall\'ee est sans cycle (par construction) ;
	\item Il y a un nombre fini de chemins sans vall\'ee entre deux noeuds, car les chemins sans vall\'ee sont \'el\'ementaires. 
\end{enumerate}
En cons\'equent, un algorithme calculant des chemins sans vall\'ee se termine.




%-------------------------------
%Suppose two arbitrary vertices $a,b$\footnote{we use the same naming convention for elements of the solution space as for vertices of the semantic graph  because each 
%vertex maps exactly one point in the solution space.} in a semantic graph $G_O$.
%There are for cases to consider, depending on the relative ordering of both solutions in $S_O$.
% If $a=b$, then the optimal path exists and has length $0$.
% If $a<b$ or $b<a$ then both nodes belongs to a chain $C$ and they are thus either directly or indirectly connected in the graph $G_O$.
%  Since a chain $C$ has a size bounded by $h$ there exists between $a$ and $b$ a path with length $h$ which is either a $(i,0,0)$-valley-free path with $i\leq h$ 
%(case $a < b$) or a $(0,0,k)$-valley-free path with $k\leq h$ (case $b < a$).
%
%The last case, is if $a \parallel b$. 
% Consider the largest chain $C_a$ containing $a$. Let be $m_{a}$ the greatest element of this chain (i.e. $a \leq m_a$ and $\fun{children}(m_a)= \varnothing$).
% A $(i,0,0)$-valley-free path of length $i\leq h$ exists between $a$ and $m_a$.
% Similarly, a $(0,0,k)$-valley-free path exists between a core element $m_b$ and $b$.
% Since the top-most solutions are fully meshed (i.e. the subgraph of maximal elements is complete),
%  then there exists an arc between $m_a$ and $m_b$ ($m_a\parallel m_b$).
%  By joining the three paths we obtain a $(i,1,k)$-valley-free path of length at most $2h+1$ to reach $b$ from $a$ \hfill \qed
%\qedhere
%\end{bproof}

%Apr\`es avoir montr\'e la terminaison des algorithmes de recherche de chemins sans vall\'ee, reste \`a montrer pour chaque requ\^ete la correction de l'algorithme associ\'e. 
%Dans le cadre de PosNet, la correction implique la satisfaction du crit\`ere 5 sur la compl\'etude des recherche :
%%\begin{itemize}
%%\item Un taux de pr\'ecision optimal : l'algorithme ne retourne que des solutions satisfaisant la requ\^ete et
%%\item Un taux de \emph{recall} optimal : 
%l'algorithme doit retourner toutes les solutions satisfaisant la requ\^ete. 
%%\end{itemize}


Les sections suivantes s'attachent \`a l'\'etude des algorithmes de recherche. 
%Pour chaque type de requ\^ete consid\'er\'e, l'algorithme associ\'e est expliqu\'e litt\'eralement, 
%puis plus pr\'ecis\'ement \`a l'aide de pseudo-code. S'en suivent la preuve de sa correction et enfin un exemple d'ex\'ecution. 
Parmi les algorithmes examin\'es, deux sont \`a 
distinguer plus particuli\`erement : l'algorithme de routage de requ\^etes exactes et l'algorithme de routage de requ\^etes par intervalles de valeurs. Ils servent de 
brique de base \`a d'autres algorithmes ; on commence donc notre pr\'esentation par ceux-l\`a.

\subsection{Routage dans l'overlay} \label{subsec:Routage dans l'overlay}
%[DANS ROUTAGE OVERLAY DETAILLER ADJ ENTRE DEUX SOUS POSET => LIEN ENTRE DEUX PAIRS]
Une requ\^ete est inject\'ee dans l'overlay en un pair quelconque. Celui-ci initie la recherche de chemins sans vall\'ee puis retransmet la requ\^ete au prochain pair. 
Lequel poursuit la recherche de chemins sans vall\'ee avant de lui-m\^eme retransmettre la requ\'ete et ainsi de suite. La requ\'ete passe donc de pair en pair, 
le choix de chaque pair (hormis le premier) \'etant d\'ecid\'e par le pair pr\'ec\'edent. Si le pair couramment travers\'e est le premier \`a \^etre visit\'e par la requ\^ete, 
alors la recherche de chemins sans vall\'ee est lanc\'ee \`a partir d'un n\oe ud du pograph arbitraire (les noeuds du pograph maximaux sont pr\'ef\'er\'es). Dans le cas o\`u 
le pair couramment travers\'e re\c coit lui-m\^eme la requ\^ete d'un autre pair, la recherche de chemins reprend au n\oe ud  du pograph d\'esign\'e par ce dernier. Ainsi, une 
requ\^ete est envoy\'ee \`a un pair $n+1$ lorsqu'au moins un chemin calcul\'e au sein du pair $n$ passe par un n\oe ud  du pograph
appartenant \`a $n+1$. La figure 
\ref{fig:semanticgraphmodifie} montre le trajet de la requ\^ete exacte $RE(5,3)$ dans un overlay compos\'e de trois pairs.           
\begin{figure}
\begin{center}
\epsfig{file=fig/semantic_graph_modifie,width=10cm}
\label{fig:semanticgraphmodifie}
\caption{Traitement de la requ\^ete $RE(5,3)$ dans un overlay compos\'e de trois pairs. Dans cet exemple, la requ\^ete est propag\'ee depuis le n\oe ud  22002, au n\oe ud
22000 puis au n\oe ud  22001.}
\end{center}
%\label{fig:4}
\end{figure}
Le d\'etail des d\'ecisions prises \`a chaque saut de la requ\^ete dans l'overlay : 
\begin{itemize}
\item{Pair 22002 : La requ\^ete p\'en\`etre dans l'overlay \`a partir du pair d'identifiant 22002 (\'etiquett\'e : pair d'entr\'ee). Celui-ci \'evalue la requ\^ete \`a partir du n\oe ud
du pograph $(4,8)$ (n\oe ud  maximal). Selon l'algorithme de r\'esolution de requ\^etes exactes (vu en \ref{subsecrequetesexactes}), la recherche se dirige vers le n\oe ud
parent (unique) de $(4,8)$ : $(9,9)$. Ce n\oe ud  du pograph appartient \`a un autre pair, d'identifiant 22000. La requ\^ete est donc retransmise \`a ce pair, avec 
l'information du n\oe ud$(9,9)$ \`a partir duquel reprendre la recherche.}
\item{pair 22000 : L'ex\'ecution de l'algorithme de recherche exacte avec $(4,8)$ \`a partir de $(9,9)$ retourne $(7,6)$, qui appartient au pair 22001, d'o\`u \`a 
nouveau saut dans l'overlay.}
\item{pair 22001 : L'\'evaluation de la requ\^ete \`a partir du n\oe ud$(7,6)$ permet de trouver la solution (apr\`es parcours d'un chemin descendant).}
\end{itemize}
%L'exemple d\'etaille ci-dessus porte sur une chemin s\'emantique passant par le core. On saisit l'occasion de 

\section{Requ\^etes exactes} \label{sec:Requetes exactes}

\subsection{Pr\'esentation g\'en\'erale de l'algorithme}

Dans le cas des requ\^etes exactes ($RE$), l'objectif est de localiser dans l'overlay le pair responsable de la solution dont la valeur de point $p_s$ est \'egale au 
point $q$ recherch\'e. Si une solution existe, elle est unique. En revanche, les handlers peuvent \^etre multiples.
Pour r\'esoudre une requ\^ete $RE$, le protocole utilise l'algorithme ci-dessous. 
L'algorithme est ex\'ecut\'e pour chaque n\oe ud  du pograph visit\'e. On appelle it\'eration une ex\'ecution de l'algorithme sur un n\oe ud  du pograph.  Chaque it\'eration correspond
 \`a une prise de d\'ecision. En fonction du r\'esultat de la comparaison entre la requ\^ete $q$ et le n\oe ud  courant $p$ (inf\'erieur, sup\'erieur, \'egal ou incomparable), une 
transition est envisag\'ee dans le pograph en comparant la requ\^ete \`a un des voisins du n\oe ud  courant. Si la transition n'introduit pas de vall\'ee, alors elle 
est valide et la requ\^ete est transf\'er\'ee : une it\'eration de l'algorithme sur le n\oe ud  destination est ex\'ecut\'ee. Dans le cas contraire, le chemin qui \'etait construit 
est abandonn\'e. La transition peut se produire selon trois directions possibles : 
\begin{itemize}
	\item Si $q$ est inf\'erieur ou incomparable \`a $p$, la requ\^ete est \og remont\'ee \fg{} dans le graphe, c'est-\`a-dire compar\'ee \`a un parent de $p$ (si $p$ en poss\`ede) ;
	\item Si $q$ est sup\'erieur, la requ\^ete est \og redescendue \fg{}, c'est-\`a-dire compar\'ee \`a un enfant de $p$ (si $p$ en poss\`ede) ; 
	\item Si $q$ est incomparable \`a un n\oe ud  maximal, la requ\^ete est diffus\'ee au sein du noyau. 
\end{itemize}
L'algorithme de routage d'une requ\^ete exacte est donn\'e ci-dessous :  
\paragraph{Pseudo-code}
\begin{tabular}{l}
\hline
\phantom{1}1\phantom{x} \textbf{if} $p$ = $q$ \textbf{then:}\\
\phantom{1}2\phantom{x}\phantom{x}\phantom{x} \textbf{return} $self$ \\
\phantom{1}3\phantom{x} \textbf{else if} $p$ > $q$ \textbf{then:}\\
\phantom{1}4\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if}  $\exists child \in children(self)$ such that $child \geq q$\\
\phantom{1}5\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{then:} \textbf{send} query to $child$\\
\phantom{1}6\phantom{x} \textbf{else if} $p || q$ or $p$ < $q$ \textbf{then:}\\ 
\phantom{1}7\phantom{x}\phantom{x}\phantom{x} \textbf{if} $last\_label = $ \{\textit{child-to-parent} or $ \varnothing$\} \textbf{then:}\\
\phantom{1}8\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if} $parents(self) \neq \varnothing$  \textbf{then:}\\
\phantom{1}9\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} $parent$ = \textbf{choose} from $parents(self)$\\
10\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{send} query to $parent$\\
11\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{else:}\\
12\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if}  $\exists peer \in peers(self)$ such that $peer \geq q$\\
13\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \, \textbf{then:} \textbf{send}  query to  $peer$\\
\hline
\end{tabular}

\subsection{Analyse de l'algorithme}
Les num\'eros de lignes indiqu\'es renvoient au code. 
\begin{itemize}  
\item Si le n\oe ud  du pograph couramment \'evalu\'e est identique \`a la requ\^ete, la solution a \'et\'e trouv\'ee (ligne 1).
\item Si le n\oe ud  est sup\'erieur \`a la requ\^ete (ligne 3), et qu'il existe un n\oe ud  enfant sup\'erieur ou \'egal \`a la requ\^ete (ligne 4), la requ\^ete est transf\'er\'ee \`a ce 
n\oe ud  enfant (forc\'ement unique) ; 
\item Si le n\oe ud  courant est incomparable ou inf\'erieur \`a la requ\^ete (ligne 6), alors trois cas sont possibles : 
\begin{enumerate}
	\item Si le dernier arc travers\'e n'est pas de type \og e>p \fg{}, alors aucun mouvement n'est entrepris ;
	\item Si le n\oe ud  courant n'est pas un n\oe ud  maximal, alors la requ\^ete est \og mont\'ee \fg{} (ligne 8-10). Plusieurs strat\'egies sont possibles pour le choix 
de l'arc ascendant. L'algorithme d\'ecrit choisit al\'eatoirement un n\oe ud  parmi les parents du n\oe ud  courant ; 
	\item Si le n\oe ud  courant est maximal, alors la requ\^ete est propag\'ee \`a un autre n\oe ud  de la clique qui contient la requ\^ete, sous r\'eserve que ce n\oe ud  existe 
(ligne 11-13). 
\end{enumerate}
\end{itemize}

 [TODO \`a r\'ediger]
%\begin{bproof}{}\\
PREUVE \\
1) Montrer que si un n\oe ud du pograph satisfait la requ\^ete, il est retourn\'e en ex\'ecutant l'algorithme\\
2) Montrer que si un n\oe ud du pograph ne satisfait pas la requ\^ete, il n'est pas retourn\'e par l'algorithme
%\end{bproof}

\subsection{Exemple}
On ex\'ecute sur notre topologie de r\'ef\'erence la requ\^ete exacte $RE(9,1)$, \`a partir du n\oe ud$(3,5)$. Le cheminement de cette requ\^ete est illustr\'e et analys\'e 
figure \ref{exemplere}, en d\'etaillant le processus de d\'ecision en chaque n\oe ud du pograph visit\'e :

\begin{figure}[!h]
\subfigure[]{\includegraphics[scale=0.6]{fig/requete_exacte_exemple}}
\subfigure[]{\begin{tabular}{>{\raggedright}p{7cm}}
\parbox[t]{6cm}{\textbf{\footnotesize 1.}{\footnotesize $(3,5)$ : La donn\'ee recherch\'ee
$(9,1)$ est incomparable \`a la valeur associ\'ee au n\oe ud  du pograph
$(3,5)$. La requ\^ete est donc transmise au n\oe ud$(4,9)$, unique parent de $(3,5)$;}\\
}\tabularnewline
\parbox[t]{6cm}{\textbf{\footnotesize 2.}{\footnotesize  $(4,9)$ : De la m\^eme mani\`ere,
$(4,9)$ \'etant incomparable avec $(9,1)$, la requ\^ete est transmise
\^a $(8,10)$. Le n\oe ud$(9,9)$ \'etait un choix possible ;}\\
}\tabularnewline
\textbf{\footnotesize 3.}{\footnotesize $(8,10)$ : $(8,10)$ est
incomparable avec $(9,1)$ et maximal. La requ\^ete est envoy\'ee \`a un voisin
de clique qui contient $(9,1)$ : $(10,1)$. $(9,9)$
est aussi un choix possible ; }\\
\tabularnewline
\textbf{\footnotesize 4.}{\footnotesize $(10,1)$ : $(10,1)$ contient la requ\^ete. De plus, il a pour n\oe ud  enfant $(9,1)$ dont la valeur associ\'ee est identique \`a 
la donn\'ee recherch\'ee : la requ\^ete est transf\'er\'ee \`a $(9,1)$ ;}\\
\tabularnewline
\textbf{\footnotesize 5.}{\footnotesize $(9,1)$ : $(9,1)$ satisfait la requ\^ete. Le processus de recherche prend donc fin.}
%\tabularnewline
%\textbf{\footnotesize 5. }{\footnotesize $(9,1)$ : On a trouv\'e un
%n\oe ud  dont la valeur associ\'ee est identique \`a la donn\'ee recherch\'ee.
%Le processus prend donc fin et la solution peut \^etre retourn\'ee. }\tabularnewline
\end{tabular}}
\caption{Simulation de l'ex\'ecution de $RE(9,1)$, \`a partir du n\oe ud$(3,5)$\label{fig:Simulation-de-l'ex=0000E9cution}\label{exemplere}}
\end{figure}

\section{Requ\^etes par intervalles} \label{sec:Requetes par intervalles}

Dans le cas des requ\^etes par intervalles, l'objectif
est de trouver dans l'overlay l'ensemble des solutions dont la valeur
est comprise entre une borne inf\'erieure $bi$ et une borne sup\'erieure
$bs$. Dans un espace de solutions \`a $n$ dimensions, si l'on d\'esigne
par $p_{i}$ la $i$-\`eme composante d'un point $p$, alors la requ\^ete
par intervalle $RI(bi,bs)$ renvoie toute solution repr\'esent\'ee par
un point v\'erifiant $bi_{i}\preceq p_{i}\preceq bs_{i}$ quelque soit $1\leq i\leq n$. 

\subsection{Pr\'esentation g\'en\'erale de l'algorithme et pseudo-code}

L'algorithme de recherche se d\'ecompose en deux \'etapes et reprend l'id\'ee g\'en\'erale du routage des requ\^etes exactes. Ces deux \'etapes sont sch\'ematis\'ees figure \ref{fig:range} 
[TODO : Franciser figure + d\'eplacer U car invisible \`a l impression] : 
% \begin{figure}[h!]
% \begin{center}
% \epsfig{file=fig/range.eps,scale=0.6}
% \caption{Chemins sans vall\'ee typique dans le cas d'une requ\^ete par intervalle. D\'ecomposition en chemin ascendant avec d\'ecouverte de $U$ et chemin descendant 
% parcourant une r\'egion de solutions comprises entre $bs$ et $bi$.\label{fig:range}}
% \end{center}
% %\label{fig:4}
% \end{figure}

\begin{figure}[!h]
\begin{center}
\centering
\includegraphics[width=0.6\textwidth]{./fig/range.png}
% conception_generique_overlay_ang.png: 346x238 pixel, 72dpi, 12.20x8.40 cm, bb=0 0 346 238
\caption{Chemins sans vall\'ee typique dans le cas d'une requ\^ete par intervalle. D\'ecomposition en chemin ascendant avec d\'ecouverte de $U$ et chemin descendant 
parcourant une r\'egion de solutions comprises entre $bs$ et $bi$.}
\label{fig:range}
\end{center}
\end{figure}

\paragraph{Etape 1 : Recherche de noeuds inform\'es. \textmd{Durant la premi\`ere \'etape, l'algorithme tente de localiser un n\oe ud$U$ sup\'erieur ou
\'egal \`a $bs$. Eventuellement, la recherche \og remonte \fg{} jusqu'\^a un n\oe ud  maximal et redescend vers $U$. Cette \'etape prend fin lorsque $U$ a \'et\'e d\'ecouvert, ou que 
la non-existence de $U$ a \'et\'e \'etablie (cas o\`u la requ\^ete est \og remont\'ee \fg{} jusqu'au noyau et que $bs$ domine tous les noeuds maximaux ou bien leur est incomparable)}}
\paragraph{Etape2 : Raffinement de la recherche. \textmd{Durant la seconde \'etape, la requ\^ete est \'elucid\'ee en routant en parall\`ele la requ\^ete le long de chemins descendants. 
Les noeuds origine de ces chemins d\'ependent du r\'esultat de l'\'etape 1 : }}
\begin{itemize}
\item Le n\oe ud$U$ si l'\'etape 1 a pu le d\'eterminer ;
\item Chaque n\oe ud  maximal contenant $bi$, dans le cas contraire.
\end{itemize}
Un chemin descendant s'interrompt lorsque le n\oe ud  du pograph en cours d'\'evaluation est inf\`erieur ou incomparable \`a $bi$. \\
Le pseudo-code de l'algorithme de guidage pour les requ\^etes par intervalles est le suivant. 

\paragraph{Pseudo-code}
\begin{tabular}{l}
\hline
\phantom{1}1\phantom{x}\textbf{if} $last\_label = $ \{\textit{child-to-parent} or $ \varnothing$\} \textbf{then:}\\
\phantom{1}2\phantom{x}\phantom{x}\phantom{x} \textbf{if} $p \ge ub$ \textbf{then:} \\
\phantom{1}3\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{for each}  $child \in children(self)$ \textbf{:}\\
\phantom{1}4\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \phantom{x} \textbf{if} $child \geq lb$ \textbf{then:} \textbf{send} query to $child$\\
\phantom{1}5\phantom{x}\phantom{x}\phantom{x}\textbf{if} $p = ub$ \textbf{then:} return $self$\\
\phantom{1}6\phantom{x}\phantom{x}\phantom{x} \textbf{else if} $parents(self) \neq \varnothing$  \textbf{then:}\\
\phantom{1}7\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} $parent$ = \textbf{choose} from $parents(self)$\\
\phantom{1}8\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{send} query to $parent$\\
\phantom{1}9\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{else:} \\
10\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{for each}  $peer \in peers(self)$ \textbf{:} \\
11\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \phantom{x}\phantom{x}\phantom{x} \textbf{if} $peer \geq lb$ \textbf{then:} \textbf{send} query to $peer$\\
12\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{for each}  $child \in children(self)$ \textbf{:}\\
13\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \phantom{x}\phantom{x}\phantom{x} \textbf{if} $child \geq lb$ \textbf{then:} \textbf{send} query to $child$\\
14\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if} $lb \le p \le ub$ \textbf{then:} \textbf{return} $self$ \\
15\phantom{x} \textbf{else:}\\
16\phantom{x}\phantom{x}\phantom{x} \textbf{for each}  $child \in children(self)$ \textbf{:}\\
17\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}  \textbf{if} $child \geq lb$ \textbf{then:} \textbf{send} query to $child$\\
18\phantom{x}\phantom{x}\phantom{x} \textbf{if} $lb \le p \le ub$ \textbf{then:} \textbf{return} $self$ \\
\hline
\end{tabular}
\selectlanguage{french}

\subsection{Analyse de l'algorithme} [TODO \`a r\'ediger]

% \begin{figure}[h!]
% \begin{center}
% \epsfig{file=fig/EquivalenceBis.eps,scale=0.5}
% \label{fig:equivalence}
% \caption{Interpr\'etation g\'eom\'etrique de l'algorithme de r\'esolution de requ\^etes par intervalle.}
% \end{center}
% %\label{fig:4}
% \end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=0.7\textwidth]{fig/EquivalenceBis.pdf}
\caption{Interpr\'etation g\'eom\'etrique de l'algorithme de r\'esolution de requ\^etes par intervalle.}
\label{fig:equivalence}
\end{figure}

% \begin{figure}[h!]
% \begin{center}
% \epsfig{file=fig/ExPosetDiscretUp,scale=0.5}
% \label{fig:exposetdiscretup}
% \caption{Interpr\'etation g\'eom\'etrique de l'algorithme de r\'esolution de requ\^etes par intervalle.}
% \end{center}
% %\label{fig:4}
% \end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=0.7\textwidth]{fig/ExPosetDiscretUp.pdf}
\caption{Interpr\'etation g\'eom\'etrique de l'algorithme de r\'esolution de requ\^etes par intervalle.}
\label{fig:exposetdiscretup}
\end{figure}

\subsection{Preuve de la correction}[TODO \`a r\'ediger]
%\begin{bproof}{}\\
PREUVE\\
1) Montrer que si un n\oe ud  du pograph satisfait la requ\^ete, il est retourn\'e en ex\'ecutant l'algorithme\\
2) Montrer que si un n\oe ud  du pograph ne satisfait pas la requ\^ete, il n'est pas retourn\'e par l'algorithme
%\end{bproof}

\subsection{Exemple}

On ex\'ecute sur notre topologie de r\'ef\'erence la requ\^ete par intervalle
$RI([4,9],[0,8])$, toujours \`a partir du n\oe ud$(3,5)$. Les bornes
$bi$ et $bs$ de la r\'egion recherch\'ee valent donc, respectivement,
$(4,0)$ et $(9,8)$. 
[TODO : Corriger labels + modifier codes couleurs (noeuds virtuels et noeuds r\'eels ne se distinguent pas) + rajouter des sens interdits ?]

\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/requete_intervalle_exemple,scale=0.6}
\label{fig:requeteintervalleexemple}
\caption{Simulation de l'ex\'ecution de $RI([4,9],[0,8])$, toujours \`a partir du n\oe ud$(3,5)$. Les \og sens interdits \fg{} indiquent les chemins \'elagu\'es par 
l'algorithme de recherche de chemins sans vall\'ee. On a fait appara\^etre (en tirets verts) la r\'egion des solutions satisfaisant la requ\^ete, entre les points $(4,0)$ et $(9,8)$}
\end{center}
%\label{fig:4}
\end{figure}

\begin{tabular}{p{8cm}p{8cm}}
\begin{tabular}{p{8cm}}
\textbf{\footnotesize Etape 1 :}{\footnotesize Recherche de $U$. On recherche un n\oe ud  du pograph $U$ \'egal ou sup\'erieur \`a $bs=(9,8)$. On note $E$ l'ensemble des 
solutions satisfaisant la requ\^ete $RI$.} \\
\hline
%\begin{itemize}
\textbf{\footnotesize $(3,5)$ :}{\footnotesize La donn\'ee recherch\'ee $(9,8)$ est sup\'erieure \`a la valeur associ\'ee au n\oe ud  du pograph $(3,5)$. La requ\^ete est donc 
transf\'er\'ee au n\oe ud$(4,9)$, parent de $(3,5)$.} %Les chemins descendants sont \'elagu\'es (que ce soit vers $(2,5)$ ou $(3,2)$) ;}\\
\textbf{\footnotesize $(4,9)$ :}{\footnotesize De la m\^eme mani\`ere, $(4,9)$ \'etant incomparable avec $(9,8)$, la requ\^ete est transf\'er\'ee au n\oe ud  parent $(9,9)$ (les 
noeuds $(8,10)$ et $(9,9)$ sont aussi \'eligibles). Une nouvelle fois, les chemins descendant sont \'elagu\'es (que ce soit vers $(1,9)$ ou $(4,2)$, m\^eme si ce dernier 
n\oe ud  fait partie de $E$) ;} \\
\textbf{\footnotesize $(9,9)$ :}{\footnotesize Puisque $(9,9)>(9,8)$, on a trouv\'e un n\oe ud$U$. L'\'etape de raffinement peut \^etre initi\'ee. $(9,9)$ poss\`ede un seul 
enfant $(9,4)$, auquel il propage la requ\^ete. Celui-ci est compris entre $bi=(4,0)$ et $bs=(9,8)$ ; il est donc ajout\'e \`a l'ensemble des solutions satisfaisant la 
requ\^ete $RI$. La recherche se poursuit via $(9,4)$. Les chemins plats sont \'elagu\'es (que ce soit vers $(8,10)$ ou $(10,1)$).}
%Notons que si cette premi\`ere \'etape s'\'etait sold\'ee par un \og \'echec \fg{} (absence de n\oe ud$U$ pour cette requ\^ete pour ce pograph), alors l'\'etape 
%suivante aurait \'et\'e ex\'ecut\'ee \`a partir de chaque n\oe ud  maximal contenant $bi$ c'est-\`a-dire dans cet exemple \`a partir de chaque n\oe ud  de la clique (aussi bien $(8,10)$, 
%$(9,9)$ que $(10,1)$ dominent $(4,0)$) ;}
%\end{itemize}
\end{tabular}
&
\begin{tabular}{p{8cm}}
\footnotesize{Notons que si cette premi\`ere \'etape s'\'etait sold\'ee par un \og \'echec \fg{} (absence de n\oe ud$U$ pour cette requ\^ete pour ce pograph), alors 
l'\'etape suivante aurait \'et\'e ex\'ecut\'ee \`a partir de chaque n\oe ud  maximal contenant $bi$ c'est-\`a-dire dans cet exemple \`a partir de chaque n\oe ud  du noyau (aussi bien 
$(8,10)$, $(9,9)$ que $(10,1)$ dominent $(4,0)$). }\\
\textbf{\footnotesize Etape 2 :}{\footnotesize Raffinement de la recherche. On recherche les solutions satisfaisant la requ\^ete.}\\
\hline
%\textbf{\footnotesize 1. }{\footnotesize $(9,4)$ : $(9,4)$ poss\`ede deux noeuds enfant, qui tous deux satisfont la requ\^ete : $(7,3)$ et $(9,1)$. Ils sont donc 
%rajout\'es \`a $E$ et la recherche se poursuit par eux ;}\\
%\begin{itemize}
\textbf{\footnotesize $(9,4)$ :}{\footnotesize $(9,4)$ poss\`ede deux noeuds enfant, qui tous deux satisfont la requ\^ete : $(7,3)$ et $(9,1)$. Ils sont donc rajout\'es \`a 
$E$ et la recherche se poursuit par eux ;}
\textbf{\footnotesize $(7,3)$ :}{\footnotesize $(7,3)$ poss\`ede un n\oe ud  enfant unique, $(4,2)$, qui est rajout\'e \`a $E$ et par lequel se poursuit le chemin. Le lien 
ascendant vers $(8,10)$ est \'elagu\'e car emprunt\'e, il cr\'eerait une vall\'ee dans le chemin passant par $(7,3)$ ;}
\textbf{\footnotesize $(4,2)$ :}{\footnotesize $(4,2)$ poss\`ede un enfant : $3,2$. Or sa valeur est incomparable \`a celle de $bi$ ; le chemin passant par $(4,2)$ est 
\'elagu\'e. Le lien ascendant vers $(4,9)$ est \'egalement \'elagu\'e car emprunt\'e, il cr\'eerait une vall\'ee dans le chemin passant par $(4,2)$ ;}
\textbf{\footnotesize $(9,1)$ :}{\footnotesize $(9,1)$ est un n\oe ud  feuille ; le chemin passant par lui est \'elagu\'e.}
%\end{itemize}
\end{tabular}
\\
\end{tabular}

\section{Requ\^etes avec joker} \label{Requetes avec joker} [TODO : \`a reprendre avec d autres valeurs]

%[MENTIONNER @article{1313212,
 %author = {Yuh-Jzer Joung and Li-Wei Yang},
% title = {Wildcard Search in Structured Peer-to-Peer Networks},
% journal = {IEEE Trans. on Knowl. and Data Eng.},
% volume = {19},
% number = {11},
% year = {2007},
% issn = {1041-4347},
% pages = {1524--1540},
% doi = {http://dx.doi.org/10.1109/TKDE.2007.190641},
% publisher = {IEEE Educational Activities Department},
% address = {Piscataway, NJ, USA},
% }, selon qui en 2007, wildcard pas trait\'ees dans structur\'e]

[REPRENDRE AVEC DES VALEUR DE L EX FILE ?]
Une requ\^ete de type \emph{wildcard} est une requ\^ete comportant au moins une valeur d'attribut \`a \og * \fg{}. On prend l'exemple de la requ\^ete $q=(TOTO,*,39,35000,*)$. 
Dans l'espace des solutions $S$ de dimension $d$ : $D=D_{1}\times D_{2}\times\ldots\times D_{d}$, une requ\^ete exacte $q=(q_{1},q_{2},\ldots,q_{d})$, 
$q\in(D_{1}\cup\{*\}\times D_{2}\cup\{*\}\times\ldots\times D_{d}\cup\{*\})$, retourne toutes les solutions satisfaisant $q$, c est \`a dire les solutions 
$s=(s_{1},s_{2},\ldots,s_{d})$ dans $S$ satisfaisant $\forall q_{j}\neq*,1\leq j\leq d,r_{j}\geq q_{j}$. 
Ainsi, l'ex\'ecution de la requ\^ete $q=(TOTO,*,39,35000,*)$ retourne toutes les donn\'ees (de dimensions 5) dont le premier attribut est TOTO, le troisi\`eme 39 et 
le quatri\`eme 35000. Les deuxi\`eme et le cinqui\`eme \'el\'ement sont non sp\'ecifi\'es (compris respectivement dans $D_2$ et $D_5$).    
Il s'agit d'un cas particulier de requ\^etes par intervalles, o\`u les valeurs d'attribut manquantes co\`uncideraient avec leur intervalle de d\'efinition respectif (la 
requ\^ete $q=(TOTO,*,39,35000,*)$ est \'equivalente \`a $q=(TOTO,D_{2},39,35000,D_{5})$). 
%Transpos\'e dans PosNet, traduire les requ\^etes de type \emph{wildcard} en requ\^etes par intervalle revient \`a interpr\'eter un joker comme un \'el\'ement minimal $\perp$. 
%Ainsi la requ\^ete $q=(TOTO,*,39,35000,*)$ s'\'ecrit elle dans PosNet $q=(TOTO,\perp,39,35000,\perp)$.  

%\section{Requ\^etes comparatives} \label{sec:Requetes comparatives} 
% : \emph{skyline} et plus proches voisins sur une dimension} \

\subsection{Requ\^etes skyline} \label{subsec:Requetes skyline} [TODO : r\'ediger l'algo] 

>>>>>>TODO : reprendre section 4 de \cite{papadias03optimal} pour les variantes sur les skyline. 

L'ensemble des solutions Pareto optimales (soit \emph{skyline}) comporte celles qui ne sont pas domin\'ees par d'autres solutions. Si l'on consid\'ere un probl\`eme de 
maximisation, une solution en domine une autre si chacune de ses composantes a une valeur \'egale ou sup\'erieure \`a la composante homologue de l'autre solution, et 
pour une composante au moins, une valeur strictement sup\'erieure. En d'autres termes, si l'on se place dans un espace des solutions \`a $d$-dimensions, une solution 
$p=(p_{1},p_{2},\ldots,p_{d})$ \emph{domine} une solution $q=(q_{1},q_{2},\ldots,q_{d})$  ssi $p_{i}\geq q_{i}$ pour $1 \leq i \leq d$ et qu'il existe au moins 
une dimension $j$ pour laquelle $p_{j}<q_{j}$.  
L'exemple suivant pr\'esente quelques cas d'usage. Le jeu de donn\'ees d\'ecrit des vols int\'erieurs en Finlande. Chaque donn\'ee est caract\'eris\'ee par quatre attributs : 
a\'eroport de d\'epart, a\'eroport d'arriv\'ee, inverse du prix, qualit\'e (attribu\'ee proportionnellement \`a la quantit\'e d'acquavit servie \`a bord :). La relation d'ordre 
d\'efinie sur la composante prix est $\leq$ : un n\oe ud  en domine un autre si est seulement si son prix est inf\'erieur ou \'egal au prix de l'autre. La figure 
\ref{fig:exrequeteskylineaeroports} pr\'esente un pograph construit \`a partir de ce jeu de donn\'ees. [TOPOLOGIE PAS TERRIBLE]
\begin{figure}[!h]
\begin{center}
\epsfig{file=fig/ex_requete_skyline_aeroports,scale=0.35}
\label{fig:exrequeteskylineaeroports}
\caption{Pograph de 17 noeuds repr\'esentant des billets de vol selon quatre crit\`eres : a\'eroport de d\'epart, a\'eroport d'arriv\'ee, inverse du prix, qualit\'e. 
Les noeuds maximaux sont repr\'esent\'es par des rectangles.}
\end{center}
\end{figure}
Des exemples de requ\^etes \emph{skyline} et les valeurs retourn\'ees sont : 
\begin{itemize}
\item $RS(POR,HEL,,)$ : L'utilisateur cherche les vols simples au d\'epart de Pori et \`a destination de Helsinki-Vantaa, qui \`a la fois minimisent le prix et maximisent 
la qualit\'e. Les valeurs retourn\'ees sont : $(POR,HEL,199,2)$. 
\item $RS(HEM,*,,)$ : L'utilisateur cherche les vols simples au d\'epart de Helsinki-Malmi, destination libre, qui minimisent le prix et maximisent la qualit\'e. 
Les destinations possibles se trouvent \^etre : Pori (POR), Joensuu (JOE) et Helsinki-Vantaa (HEL). La solution retourn\'ee est : $(HEM,JOE,399,3)$.  
\end{itemize}
Enfin, en reprenant l'exemple utilis\'e pour les requ\^etes exactes et les requ\^etes par intervalles, la requ\^ete \emph{skyline} ex\^ecut\'ee sur l'ensemble des solutions 
retourne les noeuds : ${(8,10),(9,9),(10,1)}$, c'est-\`a-dire la clique de noeuds maximaux. 

Le choix d'ordonner les solutions selon un ordre produit rend PosNet particuli\`erement adapt\'e \`a la r\'esolution des requ\^etes \emph{skyline}.
Le pseudo-code ci-apr\`es donne le d\'etail de l'algorithme : 

%\paragraph{Pseudo-code} 
%\begin{tabular}{l}
%\hline
%\phantom{1}1\phantom{x} \textbf{if} $p$ = $q$ \textbf{then:}\\
%\phantom{1}2\phantom{x}\phantom{x}\phantom{x} \textbf{return} $self$ \\
%\phantom{1}3\phantom{x} \textbf{else if} $p$ > $q$ \textbf{then:}\\
%\phantom{1}4\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if}  $\exists child \in children(self)$ such that $child \geq q$\\
%\phantom{1}5\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{then:} \textbf{send} query to $child$\\
%\phantom{1}6\phantom{x} \textbf{else if} $p || q$ or $p$ < $q$ \textbf{then:}\\ 
%\phantom{1}7\phantom{x}\phantom{x}\phantom{x} \textbf{if} $last\_label = $ \{\textit{child-to-parent} or $ \varnothing$\} \textbf{then:}\\
%\phantom{1}8\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if} $parents(self) \neq \varnothing$  \textbf{then:}\\
%\phantom{1}9\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} $parent$ = \textbf{choose} from $parents(self)$\\
%10\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{send} query to $parent$\\
%11\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{else:}\\
%12\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \textbf{if}  $\exists peer \in peers(self)$ such that $peer \geq q$\\
%13\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x}\phantom{x} \, \textbf{then:} \textbf{send}  query to  $peer$\\
%\hline
%\end{tabular}

%TODO : ETUDIER la mise-en-oeuvre dans PosNet de l'op\'erateur \emph{top-k representative skyline}. Cet op\'erateur a \'et\'e propos\'e par Lin et al. 
%[http://www.cse.unsw.edu.au/~lxue/publication/icde07b.pdf]. En pr\'esence d'un nombre potentiellement tr\`es \'elev\'e d'\'el\'ements maximaux, cet op\'erateur effectue une 
%s\'election des $k$ \'el\'ements les plus \og repr\'esentatifs \fg{}, c'est-\`a-dire des \'el\'ements qui maximisent le nombre de solutions domin\'ees.
%
%\subsection{Requ\^etes de plus proches voisins [TODO : bri\`evement]}
%\paragraph{Requ\^etes de k-plus proches voisins sur une dimension}
%\paragraph{Requ\^etes de similarit\'e par-rapport \`a un n\oe ud }
%Conversion de la distance par-rapport au n\oe ud(rayon de la boule) en termes d'intervalles pour se ramener \`a une requ\^ete par intervalle


\section{Remarques concernant l'impl\'ementation} \label{sec:remarquesimplem}
Cette section aborde quelques aspects, jug\'es d'int\'er\^et, relatifs \`a l'impl\'ementation du plan de transfert des requ\^etes.   

\paragraph{Synchronisation des pairs}
On a vu que la route d'une requ\^ete dans l'overlay \'etait calcul\'ee de mani\`ere s\'equentielle, saut par saut. Pour d\'eclencher s\'equentiellement les pairs|pour synchoniser 
les pairs, les auteurs de Chord\cite{Chord} avancent deux possibilit\'es : la mani\`ere \emph{it\'erative} et la mani\`ere \emph{r\'ecursive}. Dans le premier cas, un pair est 
d\'esign\'e \`a chaque requ\^ete et initie l'ensemble des communications qu'entra\^ine la r\'esolution de cette requ\^ete. Il est donc amen\'e \`a solliciter un par un une s\'erie de pair. 
Chacun \`a son tour, apr\`es ex\'ecution de l'algorithme de recherche appropri\'e, lui retourne \'eventuellement des solutions satisfaisant la requ\^etes et d\'esigne le prochain pair
 \`a contacter. Dans le cas r\'ecursif, chaque pair interm\'ediaire contacte lui-m\^eme le prochain pair, en lui transmettant la requ\^ete. Pour PosNet, notre choix s'est port\'e 
sur une impl\'ementation r\'ecursive. Afin d'assurer la \emph{d\'etection de la terminaison de la localisation}, chaque pair (hormis le dernier sur une route) envoie au client
 un message signalant le prochain pair travers\'e par la requ\^ete. Ainsi, le client connait il le nombre total de r\'eponses \`a attendre. La figure \ref{fig:trajetreqdiagseq} 
sch\'ematise par le biais d'un diagramme de s\'equences les interactions entre pairs dans le traitement de bout-en-bout d'une requ\^ete. 
% \begin{figure}[!h]
% \begin{center}
% \epsfig{file=fig/trajet_req_diag_seq.eps,scale=0.4}
% \label{fig:trajetreqdiagseq}
% \caption{}
% \end{center}
% %\label{fig:4}
% \end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=0.7\textwidth]{./fig/trajet_req_diag_seq}
% conception_generique_overlay_ang.png: 346x238 pixel, 72dpi, 12.20x8.40 cm, bb=0 0 346 238
\caption{}
\label{fig:trajetreqdiagseq}
\end{figure}

\paragraph{Tables de routage}
La distribution du pograph a une incidence sur les tables de routage des pairs. En plus de conna\^etre ses pairs adjacents, un pair doit en effet conna\'etre 
les noeuds s\'emantiques \og externes \fg{} (d\'etenus par un autre pair) adjacents aux noeuds s\'emantiques de sa partition du pograph. On a vu dans ce chapitre 
que la recherche des chemins sans vall\'ee peut couvrir les partitions de graphe s\'emantiques de multiples pairs. Lorsque la recherche de chemins effectu\'ee par un pair 
retourne un n\oe ud  s\'emantique situ\'e \og en-dehors \fg{} de sa partition du pograph, le pair d\'etenteur de ce n\oe ud  doit \^etre identifi\'e afin que la requ\^ete 
lui soit retransmise. Pour ce faire, chaque pair d\'etient pour chaque n\oe ud  s\'emantique \og en-dehors \fg{} de sa partition du pograph mais adjacent \`a 
celui-ci, l'information du pair qui le d\'etient. La figure \ref{fig:semanticgraph} reprend l'exemple donn\'e en \ref{fig:routageoverlay} et d\'etaille les tables de 
routage de chaque pair : 

% \begin{figure}[!h] 
% %\begin{center}
%   \subfigure[Un exemple du pograph distribu\'e sur trois pairs.]
%   {\epsfig{file=fig/semantic_graph.eps,width=7.3cm}\label{fig:semanticgraph}}
%   $\,$
% 	\subfigure[La topologie de l'overlay induit et pour chaque pair, la table de routage associant n\oe ud  s\'emantique externe et pair le d\'etenant.]
% 	{\epsfig{file=fig/ex_tables__routage.eps,width=7.3cm}\label{fig:tablesroutage}}
% %\end{center}
% \end{figure}

\begin{figure}[!h] 
  \subfigure[Un exemple du pograph distribu\'e sur trois pairs.]
{\includegraphics[width=0.5\textwidth]{./fig/semantic_graph}\label{fig:semanticgraph}}
%{\epsfig{file=fig/algorithm.png,width=6cm}\label{fig:queryrouting}}
  $\,$
	\subfigure[La topologie de l'overlay induit et pour chaque pair, la table de routage associant n\oe ud  s\'emantique externe et pair le d\'etenant.]
{\includegraphics[width=0.5\textwidth]{./fig/ex_tables__routage}\label{fig:tablesroutage}}
	%{\epsfig{file=fig/iteration.png,width=6cm}\label{fig:queryiteration}}
\end{figure}


[TODO Conclusion interm\'ediaire ?] 
 
